package com.cskaoyan.com.queue;

/**
 * 使用单向链表实现一个数据结构为队列的数据容器/集合类
 */
public class MyLinkedQueue <T> {

    private Node head; // 头结点, 队列的队头
    private Node end;  // 尾结点, 队列的队尾
    private int size;  // 存储的元素数目

    /**
     * 队列的入队列操作
     * @param value: 要入队列的内容
     * @return: 入队列是否成功
     */
    public boolean offer(T value){
        // 判断链表是否为空
        if (isEmpty()){
            // 链表为空, 新添加的内容, 既是头结点, 又是尾结点
            head = new Node(value);
            end = head;
            size++;
            return true;
        }

        end.next = new Node(value);
        end = end.next;

        size++;
        return true;
    }

    /**
     * 队列的出队列方法
     * @return: 被出的队头数据
     */
    public T poll(){
        // 队列是否为空
        if (isEmpty()){
            throw new RuntimeException("queue is empty");
        }
        // 不空

//        if (size == 1){
//            T oldValue = head.value;
//            head = null;
//            end = null;
//            size--;
//            return oldValue;
//        }

        // 保存一下原本的头结点
        T oldValue = head.value;
        // 头标记后移
        head = head.next;

        size--;
        return oldValue;
    }

    /**
     * 查看队头数据
     * @return: 队头存储的内容
     */
    public T peek(){
        // 队列是否为空
        if (isEmpty()){
            throw new RuntimeException("queue is empty");
        }
        // 不空
        return head.value;
    }


    public boolean isEmpty(){
        return size == 0;
    }


    class Node{
        T value;
        Node next;
        public Node(T value) {
            this.value = value;
        }

        public Node(T value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}
